package javaCode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created by lxy_920912 on 2017/1/13.
 */
public class NiuKe11179 {
    public TreeNode Convert(TreeNode pRootOfTree){
        Queue<TreeNode> queue = new LinkedList<>();
        if(pRootOfTree == null){
            return null;
        }
        inorderDFS(pRootOfTree,queue);

        TreeNode preNode = queue.poll();
        TreeNode first = preNode;
        while(!queue.isEmpty()){
            TreeNode q = queue.poll();
            preNode.right = q;
            q.left = preNode;
            preNode = q;
        }
        return  first;
    }
    public void inorderDFS(TreeNode root,Queue<TreeNode> queue){
        if(root != null){
            inorderDFS(root.left,queue);
            queue.add(root);
            inorderDFS(root.right,queue);
        }
    }
}
